"""
@author: wy
@file: 13.py
@time: 2023/12/7 19:06
"""
#13、使用python实现快速排序
#注意边界值
def quicksort(list,left,right):
    poval = list[left]
    while left<right:
        while (list[right]>poval and left<right):
            right -= 1
        else:
            list[left] = list[right]
            if left<right:
                left += 1

        while (list[left]<poval and left<right):
            left += 1
        else:
            list[right] = list[left]
            if left<right:
                right -= 1
    list[left]=poval
    return left

def sort(list,left,right):
    if left < right:
        pivotpos = quicksort(list, left, right)
        sort(list,0,pivotpos-1)
        sort(list,pivotpos+1,right)
    else:
        return
list1 = [23,45,67,13,4,647,85]
sort(list1,0,len(list1)-1)
print(list1)

#注意边界值
# def quicksort(list, left, right):
#     if left < right:
#         poval = list[left]
#         low = left
#         high = right
#         while low < high:
#             while list[high] > poval and low < high:
#                 high -= 1
#             else:
#                 list[low] = list[high]
#                 if low < high:
#                     low += 1
#
#             while list[low] < poval and low < high:
#                 low += 1
#             else:
#                 list[high] = list[low]
#                 if low < high:
#                     high -= 1
#
#         list[low] = poval
#         quicksort(list, left, low - 1)
#         quicksort(list, low + 1, right)
#
#     return list
#
# def sort(list, left, right):
#     if left < right:
#         sorted_list = quicksort(list, left, right)
#         return sorted_list
#     else:
#         return list





